Associative Memories to Accelerate Approximate Nearest Neighbor Search

摘要

Nearest neighbor search is a very active field in machine learning for itappears in many application cases, including classification and objectretrieval. In its canonical version, the complexity of the search is linearwith both the dimension and the cardinal of the collection of vectors thesearch is performed in. Recently many works have focused on reducing thedimension of vectors using quantization techniques or hashing, while providingan approximate result. In this paper we focus instead on tackling the cardinalof the collection of vectors. Namely, we introduce a technique that partitionsthe collection of vectors and stores each part in its own associative memory.When a query vector is given to the system, associative memories are polled toidentify which one contain the closest match. Then an exhaustive search isconducted only on the part of vectors stored in the selected associativememory. We study the effectiveness of the system when messages to store aregenerated from i.i.d. uniform $\pm$1 random variables or 0-1 sparse i.i.d.random variables. We also conduct experiment on both synthetic data and realdata and show it is possible to achieve interesting trade-offs betweencomplexity and accuracy.